package com.hanxiaozhang.no10leetcode.link;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * <p>
 * 给定一个链表，从链表尾部去掉第n个节点并且最终返回链表头部
 * 实例:
 * 给定的链表 1->2->3->4->5, n = 2. 删除末尾的第二个节点后，链表变为 1->2->3->5.
 * 注意：给定的n将始终有效。
 * <p>
 * 思路（推荐方法2的思路）：使用快慢指针
 * 1. 声明快慢指针：
 * -- 慢指针：从头结点开始的节点
 * -- 快指针：从头节点开始的n+1节点 -> 原因是：当快指针移动到尾端时，慢指针正好是需要移除节点的前一个节点。
 * 2. 快慢指针，循环每次步长一位
 * 3. 删除慢指针节点后继节点 -> 即从链表尾部去掉第n个节点
 *
 * @author hanxinghua
 * @create 2024/1/30
 * @since 1.0.0
 */
public class No19RemoveNodeFromEndList {


    public static void main(String[] args) {

        Node<Integer> head = new Node<>(1);
        head.next = new Node<>(2);
        head.next.next = new Node<>(3);
        head.next.next.next = new Node<>(4);
        head.next.next.next.next = new Node<>(5);

        // LinkUtil.whileNode(method1(head, 1));
        LinkUtil.printLink(method2(head, 1));

    }


    /**
     * 方法2：快慢指针
     *
     * @param head
     * @param n    从1开始
     * @return
     */
    private static Node method2(Node head, int n) {
        // 声明快慢指针：
        // 慢指针：从头结点开始的节点
        Node slow = head;
        // 快指针：从头节点开始的n+1节点 -> 原因是：当快指针移动到尾端时，慢指针正好是需要移除节点的前一个节点。
        Node fast = head;
        // 注意循环条件：i =0 ;i < =n
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        // 快慢指针，循环每次步长一位
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 删除慢指针节点后继节点，即 从链表尾部去掉第n个节点
        slow.next = slow.next.next;

        return head;
    }


    /**
     * 方式1
     *
     * @param head
     * @param n
     * @return
     */
    private static Node method1(Node head, Integer n) {

        Node reverse = reverse(head);
        if (n == 1) {
            reverse = reverse.next;
        } else {
            Node pre = reverse;
            while (n - 2 > 0) {
                pre = pre.next;
                n--;
            }
            pre.next = pre.next.next;
        }
        return reverse(reverse);
    }

    /**
     * 链表翻转
     *
     * @param head
     * @return
     */
    private static Node reverse(Node head) {

        Node pre = null, next = null, cur = head;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }


}
